<?xml version="1.0" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>Bio::Phylo::EvolutionaryModels - Evolutionary models for phylogenetic trees and methods to sample these
Klaas Hartmann, September 2007</title>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
<link rev="made" href="mailto:root@localhost" />
</head>

<body style="background-color: white">

<p><a name="__index__"></a></p>
<!-- INDEX BEGIN -->

<ul>

	<li><a href="#name">NAME</a></li>
	<li><a href="#synopsis">SYNOPSIS</a></li>
	<li><a href="#description">DESCRIPTION</a></li>
	<li><a href="#sampling">SAMPLING</a></li>
	<ul>

		<li><a href="#generic_sampling_interface__sample__">Generic sampling interface: <code>sample()</code></a></li>
		<li><a href="#sampling_algorithms">Sampling algorithms</a></li>
	</ul>

	<li><a href="#evolutionary_models">EVOLUTIONARY MODELS</a></li>
</ul>
<!-- INDEX END -->

<hr />
<p>
</p>
<h1><a name="name">NAME</a></h1>
<p>Bio::Phylo::EvolutionaryModels - Evolutionary models for phylogenetic trees and methods to sample these
Klaas Hartmann, September 2007</p>
<p>
</p>
<hr />
<h1><a name="synopsis">SYNOPSIS</a></h1>
<pre>
 #For convenience we import the sample routine (so we can write sample(...) instead of
 #Bio::Phylo::EvolutionaryModels::sample(...).
 use Bio::Phylo::EvolutionaryModels qw (sample);
 
 #Example#A######################################################################
 #Simulate a single tree with ten species from the constant rate birth model with parameter 0.5
 my $tree = Bio::Phylo::EvolutionaryModels::constant_rate_birth(birth_rate =&gt; .5, tree_size =&gt; 10);
 
 #Example#B######################################################################
 #Sample 5 trees with ten species from the constant rate birth model using the b algorithm
 my ($sample,$stats) = sample(sample_size =&gt;5,
                              tree_size =&gt; 10,
                              algorithm =&gt; 'b',
                              algorithm_options =&gt; {rate =&gt; 1},
                              model =&gt; \&amp;Bio::Phylo::EvolutionaryModels::constant_rate_birth,
                              model_options =&gt; {birth_rate=&gt;.5});</pre>
<pre>
                              
 #Print a newick string for the 4th sampled tree                              
 print $sample-&gt;[3]-&gt;to_newick.&quot;\n&quot;;            
 
 #Example#C######################################################################
 #Sample 5 trees with ten species from the constant rate birth and death model using 
 #the bd algorithm and two threads (useful for dual core processors)
 #NB: we must specify an nstar here, an appropriate choice will depend on the birth_rate
 #    and death_rate we are giving the model    
               
 my ($sample,$stats) = sample(sample_size =&gt;5,
                              tree_size =&gt; 10,
                              threads =&gt; 2,
                              algorithm =&gt; 'bd',
                              algorithm_options =&gt; {rate =&gt; 1, nstar =&gt; 30},
                              model =&gt; \&amp;Bio::Phylo::EvolutionaryModels::constant_rate_birth_death,
                              model_options =&gt; {birth_rate=&gt;1,death_rate=&gt;.8});
                               
 #Example#D######################################################################
 #Sample 5 trees with ten species from the constant rate birth and death model using 
 #incomplete taxon sampling
 #
 #sampling_probability is set so that the true tree has 10 species with 50% probability,
 #11 species with 30% probability and 12 species with 20% probability
 #
 #NB: we must specify an mstar here this will depend on the model parameters and the 
 #    incomplete taxon sampling parameters</pre>
<pre>
 my $algorithm_options = {rate =&gt; 1, 
                          nstar =&gt; 30, 
                          mstar =&gt; 12,     
                          sampling_probability =&gt; [.5, .3, .2]};
                   
 my ($sample,$stats) = sample(sample_size =&gt;5,
                              tree_size =&gt; 10,
                              algorithm =&gt; 'incomplete_sampling_bd',
                              algorithm_options =&gt; $algorithm_options,
                              model =&gt; \&amp;Bio::Phylo::EvolutionaryModels::constant_rate_birth_death,
                              model_options =&gt; {birth_rate=&gt;1,death_rate=&gt;.8});</pre>
<pre>
 #Example#E######################################################################
 #Sample 5 trees with ten species from a Yule model using the memoryless_b algorithm
 
 #First we define the random function for the shortest pendant edge for a Yule model
 my $random_pendant_function = sub { 
     %options = @_;
     return -log(rand)/$options{birth_rate}/$options{tree_size};
 };
 
 #Then we produce our sample
 my ($sample,$stats) = sample(sample_size =&gt;5,
                              tree_size =&gt; 10,
                              algorithm =&gt; 'memoryless_b',
                              algorithm_options =&gt; {pendant_dist =&gt; $random_pendant_function},
                              model =&gt; \&amp;Bio::Phylo::EvolutionaryModels::constant_rate_birth,
                              model_options =&gt; {birth_rate=&gt;1});</pre>
<pre>
 #Example#F#######################################################################
 #Sample 5 trees with ten species from a constant birth death rate model using the 
 #constant_rate_bd algorithm
 my ($sample) = sample(sample_size =&gt; 5,
                       tree_size =&gt; 10,
                       algorithm =&gt; 'constant_rate_bd',
                       model_options =&gt; {birth_rate=&gt;1,death_rate=&gt;.8});</pre>
<p>
</p>
<hr />
<h1><a name="description">DESCRIPTION</a></h1>
<p>This model contains evolutionary models for phylogenetic trees and 
algorithms for sampling from these models. It is a non-OO module that 
optionally exports the 'sample', 'constant_rate_birth' and 
'constant_rate_birth_death' subroutines into the caller's namespace, 
using the <code>use Bio::Phylo::EvolutionaryModels qw(sample constant_rate_birth constant_rate_birth_death);</code> 
directive. Alternatively, you can call the subroutines as class methods, 
as in the synopsis.</p>
<p>The initial set of algorithms available in this package corresponds to those in:</p>
<p>Sampling trees from evolutionary models
Klaas Hartmann, Tanja Gernhard, Dennis Wong</p>
<p>Some comments and code refers back to this paper, which is available at ... . 
Further algorithms and evolutionary are encouraged
and welcome. Simple Matlab/Octave implementations of some of these 
algorithms are also available from Klaas Hartmann on request.</p>
<p>To make this code as straightforward as possible to read some of the 
algorithms have been implemented in a less than optimal manner. The code
also follows the structure of the manuscript so there is some redundancy 
(eg. the birth algorithm is just a specific instance of the birth_death 
algorithm)</p>
<p>
</p>
<hr />
<h1><a name="sampling">SAMPLING</a></h1>
<p>All sampling algorithms should be accessed through the generic sample 
interface.</p>
<p>
</p>
<h2><a name="generic_sampling_interface__sample__">Generic sampling interface: <code>sample()</code></a></h2>
<pre>
 Type    : Interface
 Title   : sample
 Usage   : see SYNOPSIS
 Function: Samples phylogenetic trees from an evolutionary model
 Returns : A sample of phylogenetic trees and statistics from the
           sampling algorithm
 Args    : Sampling parameters in a hash</pre>
<p>This method acts as a gateway to the various sampling algorithms. The 
argument is a single hash containing the options for the sampling run.</p>
<p>Sampling parameters (* denotes optional parameters):
</p>
<pre>

 sample_size    The number of trees to return (more trees may be returned)  
 tree_size      The size that returned trees should be
 model          The evolutionary model (should be a function reference)
 model_options  A hash pointer for model options (see individual models)
 algorithm      The algorithm to use (omit the preceding sample_)
 algorithm_options A hash pointer for options for the algorithm (see individual algorithms for details)
 threads*       The number of threads to use (default is 1)
 output_format* Set to newick for newick trees (default is Bio::Phylo::Forest::Tree)
 remove_extinct Set to true to remove extinct species</pre>
<p>Available algorithms:</p>
<pre>
 b                       For all pure birth models (algorithm 1)
 bd                      For all birth and death models (algorithm 2)
 incomplete_sampling_bd  As above, with incomplete taxon sampling (algorithm 6)
 memoryless_b            For memoryless pure birth models (algorithm 4)
 constant_rate_bd        For birth and death models with constant rates (algorithm 5)</pre>
<p>Model</p>
<p>If you create your own model it must accept an options hash as its input. 
This options hash can contain any parameters you desire. Your model should
simulate a tree until it becomes extinct or the size/age limit as specified
in the options has been reached. Respectively these options are tree_size 
and tree_age.</p>
<p>Multi-threading</p>
<p>Multi-thread support is very simplistic. The number of threads you specify 
are created and each is assigned the task of finding sample_size/threads 
samples. I had problems with using Bio::Phylo::Forest::Tree in a multi-
threaded setting. Hence the sampled trees are returned as newick strings to
the main routine where (if required) Tree objects are recreated from the 
strings. For most applications this overhead seems negligible in contrast
to the sampling times.</p>
<p>From a code perspective this function (sample):</p>
<pre>
 Checks input arguments
 Handles multi-threading
 Calls the individual algorithms to perform sampling
 Reformats data</pre>
<p>
</p>
<h2><a name="sampling_algorithms">Sampling algorithms</a></h2>
<p>These algorithms should be accessed through the sampling interface (sample()).
Additional parameters need to be passed to these algorithms as described for 
each algorithm.</p>
<dl>
<dt><strong><a name="item_sample_b"><code>sample_b()</code></a></strong>

<dd>
<p>Sample from any birth model</p>
</dd>
<dd>
<pre>
 Type    : Sampling algorithm
 Title   : sample_b
 Usage   : see sample
 Function: Samples trees from a pure birth model
 Returns : see sample
 Args    : %algorithm_options requires the field:
           rate =&gt; sampling rate</pre>
</dd>
</li>
<dt><strong><a name="item_sample_bd"><code>sample_bd()</code></a></strong>

<dd>
<p>Sample from any birth and death model for which nstar exists</p>
</dd>
<dd>
<pre>
 Type    : Sampling algorithm
 Title   : sample_bd
 Usage   : see sample
 Function: Samples trees from a birth and death model
 Returns : see sample
 Args    : %algorithm_options requires the fields:
           nstar =&gt; once a tree has nstar species there should be
           a negligible chance of returning to tree_size species
           rate =&gt; sampling rate</pre>
</dd>
</li>
<dt><strong><a name="item_sample_incomplete_sampling_bd"><code>sample_incomplete_sampling_bd()</code></a></strong>

<dd>
<p>Sample from any birth and death model with incomplete taxon sampling</p>
</dd>
<dd>
<pre>
 Type    : Sampling algorithm
 Title   : sample_incomplete_sampling_bd
 Usage   : see sample
 Function: Samples trees from a birth and death model with incomplete taxon sampling
 Returns : see sample
 Args    : %algorithm_options requires the fields:
           rate =&gt; sampling rate 
           nstar =&gt; once a tree has nstar species there should be
           a negligible chance of returning to mstar species
           mstar =&gt; trees with more than mstar species form a negligible 
           contribution to the final sample.
           sampling_probability =&gt; see below.
           
sampling_probability</pre>
</dd>
<dd>
<pre>
 vector: must have length (mstar-nstar+1) The ith element gives the probability
         of not sampling i species.             
 scalar: the probability of sampling any individual species. Is used to calculate
         a vector as discussed in the paper.</pre>
</dd>
</li>
<dt><strong><a name="item_sample_memoryless_b"><code>sample_memoryless_b()</code></a></strong>

<dd>
<p>Sample from a memoryless birth model</p>
</dd>
<dd>
<pre>
 Type    : Sampling algorithm
 Title   : sample_memoryless_b
 Usage   : see sample
 Function: Samples trees from a memoryless birth model
 Returns : see sample
 Args    : %algorithm_options with fields:
           pendant_dist =&gt; function reference for generating random
           shortest pendant edges</pre>
</dd>
<dd>
<p>NB: The function pointed to by pendant_dist is given model_options
as it's input argument with an added field tree_size. It must return
a random value from the probability density for the shortest pendant
edges.</p>
</dd>
</li>
<dt><strong><a name="item_sample_constant_rate_bd"><code>sample_constant_rate_bd()</code></a></strong>

<dd>
<p>Sample from a constant rate birth and death model</p>
</dd>
<dd>
<pre>
 Type    : Sampling algorithm
 Title   : sample_constant_rate_bd
 Usage   : see sample
 Function: Samples trees from a memoryless birth model
 Returns : see sample
 Args    : no specific algorithm options but see below</pre>
</dd>
<dd>
<p>NB: This algorithm only applies to constant rate birth and death 
processes. Consequently a model does not need to be specified (and
will be ignored if it is). But birth_rate and death_rate model 
options must be given.</p>
</dd>
</li>
</dl>
<p>
</p>
<hr />
<h1><a name="evolutionary_models">EVOLUTIONARY MODELS</a></h1>
<p>All evolutionary models take a options hash as their input argument
and return a Bio::Phylo::Forest::Tree. This tree may contain extinct
lineages (lineages that end prior to the end of the tree).</p>
<p>The options hash contains any model specific parameters (see the 
individual model descriptions) and one or both terminating conditions:
tree_size =&gt; the number of extant species at which to terminate the tree
tree_age =&gt; the age of the tree at which to terminate the process</p>
<p>Note that if the model stops due to the tree_size condition then the 
tree ends immediately after the speciation event that created the last
species.</p>
<dl>
<dt><strong><a name="item_constant_rate_birth"><code>constant_rate_birth()</code></a></strong>

<dd>
<p>A constant rate birth model (Yule/ERM)</p>
</dd>
<dd>
<pre>
 Type    : Evolutionary model
 Title   : constant_rate_birth
 Usage   : $tree = constant_rate_birth(%options)
 Function: Produces a tree from the model terminating at a given size/time
 Returns : Bio::Phylo::Forest::Tree
 Args    : %options with fields:
           birth_rate The birth rate parameter (default 1)
           tree_size  The size of the tree at which to terminate
           tree_age   The age of the tree at which to terminate</pre>
</dd>
<dd>
<pre>
 NB: At least one of tree_size and tree_age must be specified</pre>
</dd>
</li>
<dt><strong><a name="item_external_model"><code>external_model()</code></a></strong>

<dd>
<p>A dummy model that takes as input a set of newick_trees and randomly samples
these.</p>
</dd>
<dd>
<pre>
 Type    : Evolutionary model
 Title   : external_model
 Usage   : $tree = $external_model(%options)
 Function: Returns a random tree that was given as input
 Returns : Bio::Phylo::Forest::Tree
 Args    : %options with fields:
           trees      An array of newick strings. One of these is returned at random.</pre>
</dd>
<dd>
<pre>
 NB: The usual parameters tree_size and tree_age will be ignored. When sampling 
     using this model the trees array must contain trees adhering to the requirements
     of the sampling algorithm. This is NOT checked automatically.</pre>
</dd>
</li>
<dt><strong><a name="item_constant_rate_birth_death"><code>constant_rate_birth_death()</code></a></strong>

<dd>
<p>A constant rate birth and death model</p>
</dd>
<dd>
<pre>
 Type    : Evolutionary model
 Title   : constant_rate_birth_death
 Usage   : $tree = constant_rate_birth_death(%options)
 Function: Produces a tree from the model terminating at a given size/time
 Returns : Bio::Phylo::Forest::Tree
 Args    : %options with fields:
           birth_rate The birth rate parameter (default 1)
           death_rate The death rate parameter (default no extinction)
           tree_size  The size of the tree at which to terminate
           tree_age   The age of the tree at which to terminate</pre>
</dd>
<dd>
<pre>
 NB: At least one of tree_size and tree_age must be specified</pre>
</dd>
</li>
</dl>

</body>

</html>
